#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

typedef struct node
{
	int data;
	node *left;
	node *right;

};
typedef node *tree;
int InsertTree(tree &root,int x)
{
	if(root != NULL)
	{
		if(root -> data == x)
			return 0;
		if(root -> data >x)
			return InsertTree(root -> left,x);
		return InsertTree(root -> right,x);
	}
	else
	{
		root = (node*)malloc(sizeof(node));
		if(root == NULL)
			return -1;
		root -> data = x;
		root -> left = root -> right = NULL;
		return 1;
	}
}

void CreateTree(tree &root)
{
	int x,n,t;
	cout<<"Nhap so node:";
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		printf("Nhap 1 node:");
		cin>>x;
		t= InsertTree(root,x);
		if (t==0) 
		{	
			cout<<"Node co roi\n";
			i--;
		}
		else 
			if (t==-1)
			{
				cout<<"Bo nho day";
				getch();
				exit(1);
			}
	}
}


void TraverseNLR(tree root)
{
	if(root!=NULL)
	{
		cout<<root->data<<"\t";
		TraverseNLR(root->left);
		TraverseNLR(root->right);
	}
}
void TraverseLNR(tree root)
{
	if(root!=NULL)
	{
		TraverseLNR(root->left);
		cout<<root->data<<"\t";
		TraverseLNR(root->right);
	}
}
void TraverseLRN(tree root)
{
	if(root!=NULL)
	{
		TraverseLRN(root->left);
		TraverseLRN(root->right);
		cout<<root->data<<"\t";
	}
}
int main()
{
	tree root;
	root=NULL;
	CreateTree(root);
	printf("\nDuyet cay theo kieu NLR:\n");
	TraverseNLR(root);
	printf("\nDuyet cay theo kieu LNR:\n");
	TraverseLNR(root);
	printf("\nDuyet cay theo kieu LRN:\n");
	TraverseLRN(root);

	getch();
	return 0;
}